量子霸权：进展解析与算法展望

作者：范桁，中科院物理所研究员，固态量子信息与计算实验室主任，Q03组长。2005年11月, 进入中科院物理所， 研究员/博士生导师。“９７３”项目课题负责人。曾在美国斯坦福大学，美国IBM研究中心，英国牛津大学，香港大学，香港中文大学，新加坡国立大学访问并展开合作研究。

谷歌人工智能量子团队近期发表了其利用超导量子处理器实现量子优势的文章，引起普遍的关注和评述，但大家对于谷歌团队在文章中具体展现了什么量子计算任务则并无详细讨论，本文依据谷歌团队文章的正文和附件，将对量子优势结果进行较为详细的解读。谷歌采取的量子计算方案被称为随机量子线路采样，即对于一个随机而确定的量子线路，通过采样方法得到比特串集合，并实现此集合中比特串的几率分布对应于量子线路的几率幅。由于是随机量子线路，经典计算机需要计算才能得到相应的结果，而对于具有53个量子比特，深度达到20个循环的量子线路，这个计算任务即使对于现今最强大的超级计算机也在短时间里没法完成，从而实现对于一类具体计算任务，量子计算机比经典计算机更强大的展示。最后将对量子优势的发展进行简单的讨论。

引言

过去几年，量子计算、 量子信息与量子模拟获得长足的发展, 但人们一直都在关心量子计算机相对于经典计算机有什么优势这个问题，短期内要实现量子计算中针对大数分解的舒尔（Shor）算法是有困难的，人们针对量子计算研究现状提出了“量子霸权”（quantum supremacy）和“量子优势”（quantum advantage）等名称各异但任务相近的目标，即针对某个计算任务，量子计算机比经典计算机更有优势，这个优势一般反映为计算速度，也可以表现为难易程度、经济性等方面，但是考虑到实用性的量子计算算法并不多，人们对具体计算任务的实用化和应用并不要求。由于国内外对于“量子霸权”这个名称存在有较多争议，后边我们都采用量子优势这个名称。

人们已经知道，量子态的希尔伯特空间是按照量子比特数成指数增长的，那么当我们实现了50个左右的量子比特数，态空间维度为  ，要存储量子态全部振幅及相位信息已经超越了计算机的内存，简单估计要在如此大的态空间来进行多步骤复杂的运算已经超越了现有计算机的能力，所以实现量子优势的一个最低要求是量子比特数超过50，否则会处于经典计算机计算能力范围之内。但是，值得指出的问题是，一个包含有多粒子的量子系统，如果考虑到多能级及噪音等因素，其态空间维数可以轻易的超过50个量子比特的情况，经典计算机已经不能利用精确对角化等计算方法来全面描述这个系统的性质，但我们不能简单的宣称这个系统就实现了量子优势。基于这样的考虑，我们应该怎样来提出一个量子优势的方案或者算法呢？

量子优势算法问题并没有明确的标准，我们可以考虑下面几点：1）是一个有明确定义的计算问题。这样经典计算机和量子计算机可以用适合自己的算法来实现，避免出现受限于特定算法路径而使二者处于不平等的地位， 即需要避免经典计算采用非最优算法这种情况。2）体现量子优势一般需要可涉及所有态空间的问题，不然经典计算机可以利用软件模拟相应算法而得到结果，导致量子优势并不明显或者不存在。3）算法结果是一个经典信息。我们考虑所有结果都需要读出，尽管有可能算法的结果是量子情况的叠加态形式，也需要用一个经典答案来比较经典和量子计算机的结果。4）需要考虑噪音对结果的影响。近期的量子计算特色可以概括为有噪音中等规模量子技术（Noisy Intermediate-Scale Quantum Technologies），在结果有一定错误率的情况下，我们需要仍然能对计算速度等进行比较。基于以上这些考虑，提出一个有说服力的量子优势算法并不容易。

最近，谷歌人工智能量子团队基于其最新发展的超导量子计算处理器，利用随机量子线路采样方案，实现了量子优势的展示，其创新点有下面几个方面：1）超导量子计算芯片采用了量子比特二维方格布局，格点上紧邻量子比特间利用可开关联结器（coupler）耦合，量子比特调控及读出线采用三维封装技术, 位于二维方格的上部对应位置。2) 量子算法为随机量子线路采样， 实验中最复杂线路利用了53个量子比特，20层循环，每层循环由每个量子比特上的随机单比特逻辑门和随后的两比特逻辑门构成。3）一个确定的线路利用量子计算机可在200秒里采样一百万次，而利用现有最强大经典计算机需要1万年，例如利用美国超算“顶点”（summit）来计算。

谷歌团队的实验是一个标志性成果，我们有以下一般性评述：1）这个结果是量子计算优势（Quantum computational supremacy）；2）所执行计算任务没有实际应用价值，而是一个展示；3）没有量子纠错，不是容错性量子计算，但这个计算任务本身允许错误发生，所以并不需要量子纠错；4）没有破解任何密码，包括量子密码；5）但意味着开始，潜在的，可以有用了, 而且并不能被经典计算机所替代！基于此平台的有实际应用价值的算法和任务将是变革性技术。

超导量子处理器结构及性能参数

谷歌团队制备了一种新的超导量子处理器，称之为“Sycamore”,这个单词原来是北美常见的一种悬铃木树的名字，该处理器集成有9行6列成方格状排列共54个量子比特，比特本身是常用的基于约瑟夫森效应的transmon量子比特，如前所述这个处理器不同之处在于量子比特的调控及读出线，并不刻蚀在量子比特布局的平面上，而是位于其上部另一层，比特层和调控层利用倒装焊封装在一起，所以是一种三维封装技术。由于边上一个量子比特不能正常工作，实验利用了53个量子比特来进行工作。

每个量子比特处于方格顶点处，处于紧邻格点的量子比特通过一个可快速开关的联结器耦合在一起，耦合强度可达40MHz, 这样设计的优点是两量子比特逻辑门利用联结器的开关来控制此较强的耦合，实验中可在12纳秒时间完成，比原来器件的两比特门快速很多，大约只有原有器件的十分之一时间，由于量子比特的平均相干时间为16微秒，完成20层循环的量子线路系统仍将具有很好的相干性，保证了算法的实现。另外联结器断开时，每个比特的操控不会影响到其它比特，所以串扰效应很低，而过去的器件则必须对串扰进行修正，对全部比特单比特门的校正需要很大的工作量。

逻辑门错误率分别在两种情况下进行标定，一种情况是仅单独考虑执行逻辑门操作的比特，另一种情况是考虑多个量子比特同时有逻辑门操作在进行，实验发现后一种情况错误率只有稍许增加，从0.15%增长为0.16%，表明多个逻辑门同时操作几乎互不影响，两比特逻辑门的错误率在单独执行和同时多个在平行执行这两种情况下分别为0.36%和0.62%，同样相互间影响较小。另外读出效率在单独和同时两种情况下分别为3.1%和3.8%。

各个逻辑门错误率相互独立对量子线路整体的保真度刻画非常关键，因为最终实现量子优势的线路并不能直接给出或者计算出明确的保真度，而是通过类比得到的估计值，这个数据的可靠性依赖于逻辑门错误率互不影响这个基本假定。

量子处理器中的超导电路包含有除了量子比特外的高能级，其多占据的几率依赖于非谐性，器件平均非谐性为-208MHz，具有较低泄露错误率。

总体来说，谷歌量子处理器各个性能参数几乎都处于世界先进水平，其中尤其是两比特门保真度很高，应该是因为其耦合器结构，另外一个突出的特点是性能参数对所有53个量子比特一致性很高，数据方差很小，表明其器件制备工艺稳定。

随机量子线路采样算法及其性质刻画

随机量子线路采样的过程和完成的任务如下：利用53个量子比特执行随机量子线路，通过测量得到系列的53位比特串，目标是得到的比特串集合其对应的量子线路振幅（几率幅）平均值大于一个特定值，比如大于全部比特串的振幅平均值。简单的说计算目标为：找出一个比特串子集，其在量子线路中的振幅较高。

前面讨论时我们已经指出，量子优势算法应涉及全部量子态空间，在全部53个量子比特上的随机量子线路即满足此条件，随机量子线路因为没有特定的结构，其量子态将包含所有可能性，导致量子线路的末态结果无法通过简单的方法或者某种特征预测，也即意味着基于此量子线路的采样问题需要量子计算机执行该线路的逻辑门操作，而经典计算机需要直接计算，从计算复杂度上来说是一个难的问题。

具体到实验，这个随机量子线路的构成为：初始化后每个量子比特随机执行一个单比特旋转门，单比特旋转门的集合由三种门构成，   ，分别为绕X轴,Y轴及X+Y轴的旋转，，随后一个量子比特通过四个联结器中的一个和其紧邻的量子比特做一个固定的两比特逻辑门，同时注意到任意两个两比特门不能同时涉及到某个比特。这样由全部比特的单比特门和部分比特的两比特门构成了量子线路的一层循环，每层循环的单比特门选取是随机的，最复杂的线路深度为m=20层循环， 共有1113个单比特门和430个两比特门。实验中，同样一种随机的线路会采样百万次左右。由于单比特门只有三种，而两比特门又受限于方格状结构，此线路并非完全随机，而是伪随机量子线路， 我们知道通用量子计算逻辑门可以由单比特任意旋转门和两比特门构成， 上述伪随机量子线路也具有一定的普适性，满足计算复杂度的要求。

执行随机量子线路操作U后，我们会得到一个维度为2⁵³维希尔伯特空间的量子态，同时对53个量子比特进行测量，得到一个53位的比特串,, 即一次采样结果，对确定的一种线路重复测量百万次，即采样百万次，结果是百万个比特串，。

现在我们来分析一下细节: 1) 53个量子比特的空间维数大约为，测量次数为， 比起维数D很小， 所以我们几乎不能的几率分布， 但是有些测量到的比特串仍然是相同的。2）按照量子力学原理，测量得到某的几率依赖于量子中的几率幅。3）实验中采样次数k也不能很大, 它是每种线路实验的重复次数。4）一个确定的量子线路定义，但是几率幅无法从实验数据中得到，同时也没有办法用计算得到，因为对于展示量子优势的线路，计是一个计算复杂度理论里难的问题。

具体来说，采样需要完成的计算任务为：给定一般的量子线路U和一个正数b，找出k个比特串，使之满足不等式，

这里b一般处于1到2之间，实验中b并不先期给定，而是依赖于实验的精度。明确的写出这个式子为：，选取的k个比特，根据公式将可得到的平均值，可以相等，所以比特串有一定的权重，尽管k数据量较小。这个任务的要求是得到的比特串所对应的线路几率幅平均值较大。

假设在采样中出现的几率为,我们将得到平均值,这个形式类似于一般的保真度的概念，但稍有不同，首先保真度是对所有D个几率求和，这里可以是一个子集，而且需强调k'指采样的k个比特串中k'个不同的比特串,另外如果是实验测量结果，应该符合量子力学原理。如果随机选取k个比特串，或者以等几率遍历所有D个比特串，我们有， 这就是b=1的情况。

我们可以分别用经典计算机和量子计算机来完成这个计算任务，当然我们已经意识到这个计算任务本身是关于量子线路计算的，所以可以自然的利用量子计算机来处理。首先考虑如果不做任何计算，而是随机的给出比特串集合，由于每个比特串的几率幅平均值是1/D, D=2⁵³，如前所述得到的不等式是b=1的情况。经典计算机可以采取矩阵计算的方法来得到不同比特串的几率幅，然后给出几率幅较大的比特串即可完成任务，但是这个计算是难的问题。一种极端情况是任选一个比特串，计算检查此比特串在给定量子线路中的振幅是否超过平均值，如果超过则全部个比特串都选此比特串，但理论已经证明，判断一个比特串的振幅值是难的计算问题。

量子计算机的计算方法为执行完量子线路后测量，测到的k个比特串就满足这个不等式，原因是如果测量量子态,需注意这是基，所以不同，而采样到有些是相同的，根据量子力学原理，我们会以较大的几率测量到几率幅较大的比特串，所以倾向于能完成这个任务，即期望值为，这里我们有k'个已归一化的，如果量子计算机不发生错误，会期望，及测量到的几率等于线路对应的几率幅,这里需考虑一个归一化因子 r 因为采样到的比特串是全部比特串的子集，测到的比特串将满足b=2，, 下面将会有详细证明。另外假设量子计算机测量次数,我们将得到全部的几率分布, 采样问题也可简单地解决。

这里小结一下，量子计算机采样得到的比特串集合将满足 b 大于1，如果随机给出比特串集合，得到的值是 b=1, 但是利用经典计算机计算在短期内达不到量子计算机同样精度的结果。

保真度与随机量子线路采样算法的联系

考虑非常特殊的量子线路U，比如 为或者Greenberger-Horne-Zeilinger （GHZ）态，，采样后得到的结果应该总是得，或者各半，理论上b会达到D或者D/2这种非常大的数字，但是一个普通的随机线路U,如果没有错误理论上的期望值为 b=2。如果噪音很大，我们测量得到任何比特串的几率都是1/D, 和随机选取比特串没有区别，所以 b=1。谷歌团队基于, 引入作为实验中类似保真度的度量，称为交叉熵保真度，对应于没有错误发生，对应于噪音导致最终的量子态实际是最大混态，类似于白噪音。下面我们来解释这些结论。

考虑噪音非常大的极端情况，即对应于最大混态，，这里 I 是单位矩阵。每个比特串在量子计算机里的实际几率幅都是1/D, 即D个几率幅全部集中于大小为1/D处，。那么如果没有噪音，一个随机线路产生的量子态其比特串几率幅分布有无规律呢？是有规律的，即尽管特定的几率幅对应的比特串是随机的，但几率幅分布本身有规律可循。

对一个随机量子线路，几率幅处于的比特串占比为,即是比特串密度（多少）按照其振幅的分布函数，这个分布函数符合Porter-Thomas分布，当然分布函数是归一化的,计算中考虑 D 较大，这个归一化式也意味着随机选取比特串将得到 b=1。现在考虑量子计算机的采样过程，几率幅处于的比特串总数为, 即量子线路的叠加态应有这样的形式，，根据量子力学原理这些比特串会以几率 p 被采样到，那么采样到的比特串个数为,即是量子计算机采样时比特串密度按照振幅的分布函数。已知采样比特串的分布函数，需要求得的平均值，可以得到，计算中已经用到 D较大这个条件，此结果意味着量子计算机如果没有错误将得到 b=2。如果需要和前面的分离变量公式相对应，可以发现这里实际是求在分布函数下的期望值。总结起来，利用量子计算机采样到的个比特串，其对应的量子线路中几率幅平均值。

所以随机量子线路中比特串个数按照振幅符合Porter-Thomas分布是采样算法中的一个基本假设，谷歌团队指出，其随机线路深度超过大约m=12时，此假设和实验符合的很好。

至此我们已经知道，随机的采样或者噪音足够强，会得到b=1, 而如果用量子计算机，理论上会得到b=2。对于有噪音的量子计算机，我们期望可以用交叉熵保真度来刻画中间情况，,  处于0与1之间，可对应于量子计算机的正确率，交叉熵的定义为：,注意是量子线路中定义的的几率幅， 而复杂线路中比特串的几率幅是计算难的问题。算法任务需要确认确定性的大于0，谷歌团队工作很重要的内容是估计交叉熵的大小。

对实现量子优势的线路，交叉熵是无法明确得到的，所以只能采取估计的方法。估计算法中需要有两个假设：1）量子计算机的所有错误的平均效果和一个退极化量子信道一致，即每个比特发生X,Y,Z三种错误的几率相等，量子态密度矩阵写为无错误密度矩阵和完全混态的几率和形式。2）所有量子门操作相互间无影响，基于这个实验的事实我们可以知道交叉熵保真度将按照循环层数m成指数衰减，而一层的交叉熵是所有逻辑门操作保真度相乘得到，即按照逻辑门数量成指数衰减。这样我们可以估计出量子优势线路的交叉熵。

为了验证这样的估计是合理而正确的，谷歌团队利用简化的量子线路作标定。可以预期量子线路的交叉熵只是和循环层数m相关，而和具体线路结构本身无关，这样可以直接把量子优势线路中53个量子比特分为相互间没有两比特门操作的两组：直接去掉横跨于两组比特间的全部或者部分两比特门,简化的线路交叉熵是明确得到的，以此作为量子优势线路交叉熵的估计值。在线路深度m较小时，估计值和真实值是近似相等的。可以确定最终的估计值是正确的，最复杂量子优势线路的线性交叉熵保真度为0.2%。

谷歌团队在200秒之内一种线路测量百万次，得到采样结果，可以使得b值从随机选取比特串的1上升到至少1.002。

如果利用经典计算机怎样来做到这样的结果呢？谷歌团队利用了不同的计算资源包括谷歌公司本身的服务器资源和美国的“顶点”超算来具体计算这个量子线路。简单的说这个计算任务是系列随机而确定的矩阵相乘作用到一个2⁵³维的向量上，最终算出向量的具体形式，采样要求找出向量中模较大的元素位置，类似于说明其在超维空间中的指向。这里矩阵对应于逻辑门，向量对应于量子比特。谷歌团队采用了数种方法来计算，如薛定谔算法对应的全振幅或者薛定谔-费曼算法先计算部分比特后黏贴为整体的方法，并估计在一个合理的时间段里，经典计算机并不能完成量子计算机同样的任务，当然在评估时间时已经考虑到交叉熵保真度的大小问题，使得互相比较处于平等条件。

谷歌在其文章中已经指出更优的经典算法会被发现，但是这个进步将会被更先进的量子处理器所超越。

量子优势算法展望与讨论

随机量子线路采样实现量子优势依赖于先期理论和实验对此问题的深入探索，在更多研究组和各种实验平台都接近实现量子优势所需要的最低要求时，除了实验技术的继续进步，方案的选择也需要更多的关注和研究。

随机量子线路采样本身当然是一个选择，可以选取不同的实现方法，比如不同于逻辑门操作，而是选取依赖于平台的易于实现的量子操作，其随机性可以施加于单比特上的旋转变换，也可选取对应于多比特量子线路中某些关联参数，但是这种选择应该满足两个条件，1）经典模拟线路是一个难的问题，2）量子计算的正确率需要准确的估计。

量子多体物理和统计的某些问题应该是大家期待的方案，也具有科学价值，具体可以考虑与自旋玻璃基态相关的课题，比如利用量子退火算法和经典蒙卡计算的比较。与量子化学、机器学习和大数据等结合的量子计算方案，也是非常有前景的选择。

应该说明确刻画一个量子计算机易于解决而经典计算机难于计算的问题本身是一个创新性问题，相信更多研究人员的关注会促进这个方向的发展。

谷歌团队也研究了测量统计涨落和不确定度问题，对经典计算机的计算时间的估计问题，测量效率问题等。当然值得讨论的问题也很多，比如线路构造的随机性问题，随机线路比特串几率幅分布的统计问题，交叉熵保真度还较小问题等等，但是技术的进步是显然的，算法的每种选择总会带来相应的问题，这些问题都是今后这个方向后续工作的价值。最后说明一下，解读不能替代对原文的阅读，也许解读本身就是某种曲解。

致谢：感谢物理所向涛院士，许凯副研究员，国科大张富春教授，苏刚教授，天津大学李新奇教授，浙江大学王浩华教授，物理所研究生葛自勇，孙政杭等就相关课题所进行的多次深入讨论。笔者曾在不同场合数次讲解讨论过谷歌团队的文章，尽管谷歌团队的文章有详细的结果展示，笔者仍希望中文解析和展望文章能有助于大家对谷歌进展的了解。

参考文献

[1] Arute F et al., Quantum supremacy using a programmable superconducting processor, 2019 Nature. 574 505，and Supplementary Information. 

-End-

1930年秋，第六届索尔维会议在布鲁塞尔召开。早有准备的爱因斯坦在会上向玻尔提出了他的著名的思想实验——“光子盒”，公众号名称正源于此。